How to allocate spectra to users efficiently and improve the revenue of providers are popular research topics recently. To address the problem of low revenue of providers in spectrum combinatorial auctions, Random Walk for Spectrum Combinatorial Auctions (RWSCA) mechanism was designed to maximize the revenue of spectrum providers by combining the characteristics of asymmetric distribution of user valuations. First, the idea of virtual valuation was introduced, the random walk algorithm was used to search for a set of optimal parameters in the parameter space, and the valuations of buyers were linearly mapped according to the parameters. Then, VCG (Vickrey-Clarke-Groves) mechanism based on virtual valuation was run to determine the users who won the auction and calculate the corresponding payments. Theoretical analysis proves that the proposed mechanism is incentive compatible and individually rational. In spectrum combinatorial auction simulation experiments, the RWSCA mechanism increases the provider’s revenue by at least 16.84%.